package classic;

/**
 * fibonacci函数的非递归解法
 * fibonacci函数满足以下规律：
 * f(0) = 0; f(1) = 1;
 * f(n) = f(n-1) + f(n-2);
 * 可以方便地用递归解决，但是递归的效率特别低，特别是n很大时
 * 不难发现很多中间结果其实是重复了，如果用递归则每次都重复计算，
 * 所以效率很低，可以用循环的方法来代替递归，并保存中间结果，从而更高效
 *
 * @author zj
 */
public class FibonacciFunction {
    public static void main(String[] args) {
        int n = 45;
        long t0 = System.currentTimeMillis();
        System.out.println(fibonacci1(n));
        long t1 = System.currentTimeMillis();
        System.out.println("耗时：" + (t1 - t0));
        System.out.println(fibonacci2(n));
        System.out.println("耗时：" + (System.currentTimeMillis() - t1));
    }

    //递归方法
    private static int fibonacci1(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci1(n - 1) + fibonacci1(n - 2);
        }

    }

    //非递归方法，使用循环，并保存了中间结果，效率明显提升
    private static int fibonacci2(int n) {
        int first = 0;
        int second = 1;
        if (n == 0) {
            return first;
        } else if (n == 1) {
            return second;
        } else {
            int res = 0;
            for (int i = 2; i <= n; i++) {
                res = first + second;
                first = second;
                second = res;
            }
            return res;
        }
    }
}
